路由是选择路径并将报文沿着选择的路径进行转发的过程。

1. 路由器

1.1 路由器功能

路由器从功能上可以划分为：

  • 路由选择：使用路由协议（或手工静态配置的方式）获取整个网络的拓扑结构，构造、维护路由表。
  • 分组转发：分组转发结构由交换结构、一组输入端口和一组输出带端口构成。
    1. IP分组检查：检查版本号，检查分组头字段，计算头校验和。
    2. 目的IP地址分析与路由表查找：决定分组的输出接口和到达目的IP地址的下一跳节点。
    3. 分组TTL控制：路由器调整TTL值字段，防止分组在网络中无终止循环。本地递交的分组TTL值要大于0。对于向外转发的分组，首先TTL值减去1，在实际转发之前还要重新检查TTL值。TTL值过期的分组要丢掉，同时还可能向分组的发送者通告错误信息。
    4. 校验和计算：TTL字段的变化，要求重新计算校验和。
    5. IP分片：为了适应输出网络接口的MTU(Maximum Transmission Unit)值，有时需要分片处理。分片对性能的影响比较大，现在由于PMTU技术的应用，分片操作并不多见。

PMTU

对于IPv4包，路径MTU发现通过在传出包的IP头中设置Don't Fragment (DF)标志位来工作。然后，任何路径上MTU小于数据包的设备都将丢弃它，并返回包含其MTU过大的ICMPv4(类型3、代码4)数据包，从而允许源主机适当地减小其路径MTU。

1.2 路由分组转发过程

  1. 从数据报的首部提取目的主机的 IP 地址 D，得到目的网络地址N
  2. 若 N 就是与此路由器直接相连的某个网络地址，则进行直接交付
  3. 若路由表中有目的地址为 D 的特定主机路由，则把数据报传送给表中所指明的下一跳路由器
  4. 若路由表中有到达网络 N 的路由，则把数据报传送给路由表中所指明的下一跳路由器
  5. 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器
  6. 报告转发分组出错

路由选择

路由选择使用CIDR技术，通过最长前缀匹配来定位最精准的一条路由信息。

2. 路由协议

路由选择协议都是自适应的，能随着网络通信量和拓扑结构的变化而自适应地进行调整。互联网可以划分为许多较小的自治系统（Autonomous system, AS），不同的AS可以采用不同的路由选择协议。路由选择协议主要可以分为两大类：

  • 内部网关协议（Interior Gateway Protocol，IGP）：RIP、OSPF和IS-IS
  • 外部网关协议（Exterior Gateway Protocol，EGP）：BGP

2.1 内部网关协议

2.1.1 RIP

（一）简介

RIP （Routing Information Protocol，路由信息协议）是一种基于距离向量的路由选择协议。距离是指跳数，设备到与他直连网络的设备跳数为0，然后每经过一个三层设备跳数增加1，也就是度量值等于从本网络到达目网络间的三层设备数量。跳数最多为 15，超过 15 表示不可达。

由于RIP的实现较为简单，在配置和维护管理方面也远比OSPF和IS-IS容易，因此RIP主要应用于规模较小的网络中，例如校园网以及结构较简单的地区性网络。对于更为复杂的环境和大型网络，一般不使用RIP协议

RIP通过UDP报文进行路由信息的交换，使用的端口号为520。所以它又是一个不可靠的路由协议。

（二）更新机制

RIP协议有两种更新机制：定期更新和触发更新。定期更新是根据设置的更新计时器定期发送RIP路由通告。而触发更新是RIP路由器一旦察觉到网络变化，就尽快甚至是立即发送更新报文，而不等待更新周期结束。只要触发更新的速度足够快，就可以大大地防止“计数到无穷大”的发生，但是这一现象还是有可能发生的。

RIP路由环路问题

详见引用1

两种更新机制都遵循相同的更新规则：

  1. 如果更新的某路由表项在路由表中没有，则直接在路由表中添加该路由表项
  2. 如果路由表中已有相同目的网络的路由表项，且来源端口相同，那么无条件根据最新的路由信息更新其路由表
  3. 如果路由表中已有相同目的网络的路由表项，但来源端口不同，则要比较它们的跳数，将跳数较小的一个作为自己的路由表项
  4. 如果路由表中已有相同目的网络的路由表项，且跳数相等，保留原来的路由表项
  5. 若 3 分钟还没有收到相邻路由器的更新路由表，则把该相邻路由器标为不可达，即把距离置为 16
（三）示例

  1. 所有路由器中的路由表都只有和自己直接连接的网络的路由表项。

  1. 各路由器就会按设置的周期（默认为30秒）向相邻路由器发送路由更新。具体哪个路由器会先发送路由更新，取决于哪个路由器先开。现假设路由器R2先收到来自路由器R1和R3的路由更新，然后就更新自己的路由表，添加了分别通过R1和R3到达10.0.0.0/8网络和13.0.0.0/8网络的路由表项，跳数加1。

  1. R2更新自己的路由表后，会把完整的路由表发给邻居路由器R1和R3。路由器R1和R3分别再进行更新。

  1. 这个过程会按照固定时间间隔不断更新，最终路由表会趋向于收敛

2.1.2 OSPF

（一）简介

OSPF（Open Shortest Path First，开放式最短路径优先）是大中型网络上使用较为广泛的内部网关协议，使用“代价（Cost）”作为路由度量。OSPF采用Dijkstra算法（SPF算法）来计算最短路径树。与RIP和BGP不同的是，OSPF协议不使用TCP或者UDP协议而是直接承载在IP协议之上。

（二）Cost代价

每个路由器都把自己当做Dijkstra算法的根，通过累计cost来计算达到目的地的最短路径。默认情况下，路由器根据接口的配置带宽来计算cost，带宽越高，开销越低，计算公式如下。最终cost是对路径上每一个路由器的入接口的cost值累加得到的。

（三）工作过程
  1. 每台路由器和直接相连的路由器互交，发送Hello报文，建立邻居关系。
  2. 每台路由器构建包含直接相连的链路状态的LSA（Link-State Advertisement，链路状态通告）。链路状态通告(LSA)中记录了所有相关的路由器，包括邻路由器的标识、链路类型、带宽等。
  3. 每台路由器泛洪链路状态通告（LSA）给所有的邻路由器，并且自己也在本地储存邻路由发过来的LSA，然后再将收到的LSA泛洪给自己的所有邻居，直到在同一区域中的所有路由器收到了所有的LSA。每台路由器在本地数据库中保存所有收到的LSA副本，这个数据库被称作”链路状态数据库（LSDB，Link-State Database）”。
  4. 每台路由器基于本地的”链路状态数据库(LSDB)”执行”最短路径优先（SPF）”算法，并以本路由器为根，生成一个SPF树
  5. 基于SPF树计算去往每个网络的最短路径，得到最终的路由表。

优缺点

路由器通过LSA的交换，最后独立的计算出到每个网络的最短路径，相对RIP具有更强的全局观，收敛速度更快。当检测到拓扑发生变化时立即发送更新，链路状态实时性更强。但SPF算法复杂度更高，对内存需求高，同时在网络初始化时，大量链路状态包泛洪，会影响网络的可用带宽。

（五）区域

一个OSPF网络分为多个区域。区域将网络中的路由器在逻辑上分组并以区域为单位向网络的其余部分发送汇总路由信息。区域是以接口（Interface）为单位来划分的，所以一台多接口路由器可能属于多个区域。相同区域内的所有路由器都维护一份相同的链路状态数据库（LSDB），如果一台路由器属于多个区域，那么它将为每一个区域维护一份LSDB。常见的区域类型有如下几种：

  1. 骨干区域：骨干区域是整个OSPF的核心区域。所有其他非骨干区域必须和骨干区域直接或间接相连。骨干区域的功能是在不同的非骨干区域之间分发路由信息。骨干区域必须是唯一而且连续的，但不需要在物理上连续，可以使用虚拟连接。
  2. 传送区域：传送区域连接至少2个其他区域，它将通告从一个区域传送到另一个区域。
  3. 末梢区域：末梢区域是一个不允许AS外部路由通告（AS External LSA，即类型5 LSA）在其内部进行洪泛扩散的区域。末梢区域的区域边界路由器会通告一条默认路由（default route）到该区域内所有路由器，任何发往AS外部网络的数据流都将依据默认路由来转发。

将一个网络划分为多个区域有以下优点：

  • 某一区域内的路由器只需要维护该区域的LSDB，而不用维护整个OSPF网络的链路状态数据库。
  • 将某一区域网络拓扑变化的影响限制在该区域内，不会影响到整个OSPF网络，从而减小OSPF计算的频率。
  • 将链路状态通告（LSA）的洪泛限制在本区域内，从而降低OSPF协议产生的数据量。
  • 划分区域可以对网络进行层次化结构设计。
  • 划分区域有利于资源合理调配，核心区域部署性能较好的设备资源，边缘区域部署性能较差的设备资源即可。
（六）路由器类型
  1. 内部路由器：一台路由器上所有启动了OSPF的接口都在同一区域
  2. 骨干路由器：骨干路由器是指至少有一个启用了OSPF的接口是和骨干区域相连的路由器。骨干路由器也可以同时是区域边界路由器或自治系统边界路由器
  3. 区域边界路由器：区域边界路由器是指连接一个或者多个区域的路由器。区域边界路由器为每一个与之相连的区域维护一份链路状态数据库，因此区域边界路由器需要比内部路由器更多的内存资源和更高性能的处理器。
  4. 自治系统边界路由器： 自治系统边界路由器用来把从其他路由协议学习到的路由以路由重分发的方式注入到OSPF进程中，从而使得整个OSPF域内的路由器都可以学习到这些路由（除了末梢区域内的路由器）。一台自治系统边界路由器可以是OSPF域内非末梢区域的任何路由器，它可以是内部路由器、区域边界路由器、骨干路由器。

2.2 外部网关协议BGP

BGP（Border Gateway Protocol，边界网关协议）是是互联网上一个核心的去中心化自治路由协议。当网络过大的时候，会导致路由表过大而难以维护，这时候采用分治的方法，将一个大网络划分为若干个小网络，这些小网络称为自治系统(AS)，BGP的诞生就是用于自治系统间的通信。它通过维护IP路由表或前缀表来实现自治系统（AS）之间的可达性，属于矢量路由协议。大多数互联网服务提供商必须使用BGP来与其他ISP创建路由连接，特大型的私有IP网络也可以使用BGP，将若干个大型的OSPF网络进行合并。

BGP是应用层协议，其传输层使用TCP，默认端口号是179。TCP连接的窗口是65K字节，也就是说TCP连接允许在没有确认包的情况下，连续发送65K的数据。而其他的路由协议，例如OSPF的窗口只有一个数据包，也就是说前一个数据包收到确认包之后，才会发送下一个数据包。当网络规模巨大时，需要传输的数据也相应变大，这样效率是非常低的。这也是它不适合大规模网络的原因之一。而正是由于TCP可以可靠的传输大量数据，且互联网的路由信息是巨大的，TCP被选为BGP的传输层协议，并且BGP适合大规模网络环境。

2.2.1 IBGP与EBGP

BGP有两种邻居，其中运行在同一个AS内的BGP邻居称为IBGP(Interior BGP)，不同AS间的邻居称为EBGP(Exterior BGP)，注意无论是IBGP或者EBGP，上面都必须运行着BGP协议。当一家ISP与至少两家ISP交换路由的时候会用的ASN，每个AS都有自己独特的AS号码(ASN)。

2.2.2 路由注入和通告

BGP路由器的路由注入和通告都是为了修改BGP路由表。当路由器之间建立BGP邻居之后，就可以相互交换BGP路由。一台运行了BGP协议的路由器，会将BGP得到的路由与普通路由分开存放，所以BGP路由器会同时拥有两张路由表：

  • IGP路由表：通过show ip route查看，存放通过IGP协议或手工配置得到的普通路由表
  • BGP路由表：通过show ip bgp查看，运行BGP之后创建的路由表。BGP路由表的路由信息只能传递给BGP协议，如果两台BGP邻居的BGP路由表为空，就不会有任何路由传递。
（一）BGP路由表注入
  • 纯动态注入：路由器将通过IGP路由协议动态获得的路由信息直接注入到BGP中。
  • 半动态注入：路由器有选择的将IGP路由协议获得的动态路由信息注入到BGP中。
  • 静态注入路由器将静态配置的某条路由注入到BGP系统中。
（二）BGP路由通告

在BGP路由表注入路由后，BGP路由器之间会将这些路由在BGP路由器间进行通告。通告要遵守以下规则：

  • BGP 路由器只把自己使用的路由通告给相邻体
  • BGP 路由器从EBGP获得的路由会向它的所有BGP相邻体通告（包括EBGP和IBGP）
  • BGP路由器从IBGP获得的路由不会向它的IBGP相邻体通告（避免内部产生环路）
  • BGP 路由器从IBGP获得的路由是否通告给它的EBGP相邻体要依IGP和BGP同步的情况而定

2.2.3 路径属性

在默认情况下，到达同一目的地，BGP只走单条路径，并不会在多条路径之间执行负载均衡。对于IGP路由协议，当有多条路径可以到达同一目的地时，则根据最小metric值来选择最优路径，而 BGP 存在多条路径到达同一目的地时，对于最优路径的选择，BGP并不会以metric值大小为依据，BGP对于最优路径的选择，需要靠比较路由条目中的路径属性，只有在比较多条路由的属性之后，才能决定选择哪条为最优路径。

BGP的路径属性可以划分为以下四类：

  • 公认强制 （Well-Known Mandatory）:所有的路由中都需要写入公认强制属性。如Origin，Next Hop，AS path。
  • 公认自选 （Well-Known Discretionary）：能够理解和支持即可，不一定要写入路由
  • 可选可传递 （Optional Transitive）：不一定要理解或支持
  • 可选不可传递（Optional Nontransitive）：只有特定的BGP路由器才能理解和传递

对于任何一台运行BGP的路由器，都必须支持公认强制属性，并且在将路由信息发给其它BGP邻居时，必须在路由中写入公认强制属性，这些属性是被强制写入路由中的，一条不带公认强制属性的路由被BGP路由器被视为无效而被丢弃，一个不支持公认强制属性的BGP，是不正常的，不合法的BGP。

（一）origin

origin属性为起源属性，描述路由是以何种方式注入到BGP路由表中的，主要有以下两种情况:

  • 以 network 命令注入到BGP路由表中，origin 属性为 IGP
  • 以 redistribute 命令注入到BGP路由表中，origin 属性为 Incomplete

warning

IGP优先级比Incomplete高

（二）Next Hop

指示下一个AS的路由器入口的网段，同一个AS内Next hop的值不变

（三）As Path

描述了该路由经过的AS组成的路径，AS路径中不能算上自己的AS，从离自己最近的AS开始，以目的网络的AS结束。下图为 AS5 到 AS1 的路由的AS Path属性：

借助路由的AS Path属性，可以避免环路，具体操作就是收到一条AS Path属性中含有自己AS的路由的时候丢弃该路由。在选路的时候，优先选As Path最短的那条，如果As Path距离相等，则优选本AS内到出口路由器最短的那根，如果还相等，则选择Router_ID（发送路由的路由器）最小的那根

3. 引用

  1. RIP环路问题总结
  2. RIP路由协议
  3. OSPF协议详解
  4. BGP漫谈
  5. 计算机网络课程总结—BGP协议